/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.fa;

import java.util.List;

import mosdi.util.BitArray;
import mosdi.util.SingletonList;

public class GeneralizedStringsNFA extends NFA {

	private BitArray startMask;
	private BitArray acceptMask;
	private BitArray[] transitionMasks;
	private int alphabetSize;
	
	public GeneralizedStringsNFA(GeneralizedString s) {
		this(new SingletonList<GeneralizedString>(s));
	}

	/** Constructs an NFA that finds all matches of a set of generalized strings.
	 *  @param list All generalized string must be over the same alphabet. */
	public GeneralizedStringsNFA(List<GeneralizedString> list) {
		if (list.isEmpty()) throw new IllegalArgumentException("List is empty.");
		this.alphabetSize = list.get(0).getAlphabet().size();
		int stateCount = 0;
		for (GeneralizedString gs : list) {
			stateCount += gs.length()+1;
			if (gs.getAlphabet().size()!=alphabetSize) throw new IllegalArgumentException("Alphabet size mismatch.");
		}
		startMask = new BitArray(stateCount);
		acceptMask = new BitArray(stateCount);
		transitionMasks = new BitArray[alphabetSize];
		for (int c=0; c<alphabetSize; ++c) {
			transitionMasks[c] = new BitArray(stateCount);
		}
		int n = 0;
		for (GeneralizedString gs : list) {
			startMask.set(n, 1);
			acceptMask.set(n+gs.length(), 1);
			for (int i=0; i<gs.length(); ++i) {
				BitArray genChar = gs.getPosition(i);
				for (int c=0; c<alphabetSize; ++c) {
					if (genChar.get(c)) transitionMasks[c].set(n+i+1, 1);
				}
			}
			n += gs.length()+1;
		}
	}
	
	@Override
	public BitArray acceptStates() {
		return acceptMask;
	}

	@Override
	public int alphabetSize() {
		return alphabetSize;
	}

	@Override
	public BitArray startStates() {
		return startMask;
	}

	@Override
	public int stateCount() {
		return startMask.size();
	}

	@Override
	public BitArray transition(BitArray activeStates, int character) {
		BitArray b = new BitArray(activeStates);
		b.shiftLeft();
		b.and(transitionMasks[character]);
		b.or(startMask);
		return b;
	}

	/** Returns the set of active states after reading one wildcard character; 
	 *  i.e. all states that are reachable in one step are activated. */
	public BitArray readWildcard(BitArray activeStates) {
		BitArray b = new BitArray(activeStates);
		b.shiftLeft();
		b.or(startMask);
		return b;
	}
	
	/** Returns the number of matching generalized strings. */
	@Override
	public int matchCount(BitArray states) {
		BitArray b = new BitArray(states);
		b.and(acceptStates());
		return b.numberOfOnes();
	}

}
